An Internet path connecting two hosts can consist of multiple routers and physical links. A capacity of an individual link can be thought of as the maximum rate at which packets can be transmitted over the link. At any given time, the link's available bandwidth is its unused residual capacity. The capacity of an end-to-end path can be the minimum capacity among its constituent links. The path's available bandwidth is defined in a similar way. The present concepts relate to determining communication speeds, such as available bandwidths and/or capacities, in ad-hoc distributed groups.
There are many tools that estimate the available bandwidth along an end-to-end path. Some of these bandwidth estimation tools are discussed below. The present concepts can utilize bandwidth information from specifically mentioned bandwidth estimation tools or other tools. Most of these bandwidth estimation tools use one of two techniques. In a packet rate method, a source generates traffic at a variety of speeds, and the receiver reports its observed download rates. Above a certain transmission speed, a bottleneck link will become saturated, causing the receiving rate to fall below the sending rate. The available bandwidth is the lowest transmission rate which triggers this congestion. Named examples of this packet rate tool include packet transmission rate (PTR), pathload, trains of packet pairs (TOPP), and pathchirp.
In a packet gap method, a sender issues multiple packet pairs, carefully controlling the spacing between two packets in a pair. Assuming that the end-to-end path has a single bottleneck, any receiver-measured increase in the packet gap is due to cross-traffic at the bottleneck. Armed with the gap increase and the path capacity, one can calculate the volume of the cross-traffic and then the remaining available bandwidth. Named tools that use the packet gap technique include initial gap increasing (IGI), Delphi, and Spruce.
Another technique termed “BRoute” attempts to minimize probing traffic by exploiting two observations. First, most bottleneck links reside at the edge of the network. Second, in large systems, each edge link is likely to be shared by multiple end-to-end paths. By only probing edge links, BRoute can identify most sources of congestion without exhaustive introspection of each link in a path. Furthermore, the probing cost for each edge segment is amortized across the set of peers which use that segment.
Unlike the other tools described above, BRoute uses dedicated network infrastructure where hosts discover their edge links by issuing traceroutes to well-known landmark nodes. BRoute also uses border gateway protocol (BGP) data to determine which edge segments connect end hosts. The present concepts generally relate to ad-hoc groups, meaning that dedicated infrastructure is unlikely to exist. Often the ad-hoc groups are composed of “regular” end-users who lack access to privileged BGP feeds utilized by the BRoute tool.
Like all measurement tools, the above mentioned bandwidth estimators do not generate perfectly accurate results. Some of the measurement error arises from the simplifying assumptions embedded in the design of the tools. For example, tools often assume that all routers use a first-in-first-out (FIFO) queuing discipline, and that the volume of cross-traffic is stationary. Resource constraints on the measurement hosts can also cause poor estimations. In particular, many tools utilize fine-grained timers to control the rate at which packets are sent. They also use accurate timestamps for received packets. On highly loaded machines, the operating system (OS) may be unable to provide the necessary fidelity. Even a lightly loaded machine may underestimate a high-capacity link if the native timestamp resolution is too coarse.
Because of these issues, the output of a bandwidth estimation tool should not be taken as ground truth. For example, pathchirp underestimates available bandwidth when the volume of cross-traffic is low, but overestimates when cross-traffic is high. Bandwidth estimates are also sensitive to the size of probe packets, but different paths may be optimally measured with different packet sizes, and generating this mapping is not straight forward. Thus, measurement jitter is often non-trivial—in controlled settings, the standard deviation of measurement can be 30% or more.